package com.HaFuManShu2;

import java.util.Scanner;

public class HuffmanTree <T>{
    Node<T>[] ht;
    String[] hc;
    int n;
    public HuffmanTree(int n){
        ht = new Node[2*n-1];
        hc = new String[n];
        this.n = n;
    }

    /**
     * 选择权重最小的节点
     * @param m
     * @return
     */
    public int selectMin(int m){
        // 在0-m-1号单元范围内选择权值最小的根节点
        int k,i;
        for (i = 0; i < m && ht[i].parent != -1 ; i ++);
        k = i;
        for (i++;i<m;i++){
            if (ht[i].parent == -1 && ht[i].weight < ht[k].weight){
                k = i;
            }
        }
        ht[k].parent = -2;
        return k;
    }

    /**
     * 将单一节点创建成一个颗树
     */
    public void createTree(){
        int i;
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入" + this.n + "个元素及权值（元素输入后回车输入权值依次循环输入n个元素）:");
        for (i = 0; i < n; i++) {
            T d = (T)sc.next();
            double w = sc.nextDouble();
            ht[i] = new Node<>(d,w,-1,-1,-1);
        }
        for (; i < this.ht.length; i++) {
            int s1 = selectMin(i);
            int s2 = selectMin(i);
            ht[s1].parent = ht[s2].parent = i;
            ht[i] = new Node<T>(null,ht[s1].weight + ht[s2].weight,-1,s1,s2);
        }
    }


    /**
     * 进行哈夫曼编码
     */
    public void createCode(){
        char[] cd = new char[n-1];
        for (int i = 0; i < n; i++) {
            // 对n个叶子求哈夫曼编码
            // 求i号叶子节点的哈夫曼编码
            int start = n - 2;
            for (int c = i,f = ht[c].parent; f != -1;c = f,f = ht[c].parent){
                if (c == ht[f].lchild){
                    cd[start--] = '0';
                }else {
                    cd[start--] = '1';
                }
            }
            hc[i] = new String(cd,start+1,n-start-2);
        }
    }

    /**
     * 展示树
     */
    public void displayTree(){
        for (int i = 0; i < this.ht.length; i++) {
            System.out.println(ht[i].data + "\t" + ht[i].weight + "\t" + ht[i].parent + "\t" + ht[i].lchild + "\t" + ht[i].rchild);
        }
    }

    /**
     * 展示编码
     */
    public void displayCode(){
        for (int i = 0; i < this.n; i++) {
            System.out.println(ht[i].data + ":" + hc[i]);
        }
    }

    /**
     * 电文编码
     * @param text
     * @return
     */
    public String textCode(String text){
        // 将要发送的电文text进行编码后返回
        String codeStr = "";
        for (int i = 0; i < text.length(); i++) {
//            char ch = text.charAt(i);
            String ch = String.valueOf(text.charAt(i));
            int k;
            for (k = 0;k < this.n;k++){// 将字符hc替换为对应的哈夫曼编码
                if (ch.equals(ht[k].data)){
                    codeStr += hc[k];
                    break;
                }
            }
        }
        return codeStr;
    }

    /**
     * 电文解码
     * @param text
     * @return
     */
    public String textDecode(String text){
        // 将接收到的电文text译码,得到电文原文
        String decodeStr = "";
        for (int i = 0; i < text.length();) {
            // 反复从根到叶子,翻译一个字符
            int p = this.ht.length - 1;// 从根开始
            while(ht[p].lchild != -1 && ht[p].rchild != -1){
                char ch = text.charAt(i);
                if (ch == '0'){
                    p = ht[p].lchild;
                }else {
                    p = ht[p].rchild;
                } //
                i++;
            }
            decodeStr += ht[p].data;
        }
        return decodeStr;
    }
}

